/**
 * https://leetcode.cn/problems/majority-element/?envType=study-plan-v2&envId=top-100-liked
 * 寻找数组中的多数元素
 * 多数元素定义为在数组中出现次数超过数组长度一半的元素
 * 双循环，log(n^2)
 * @param {number[]} nums - 包含整数的数组
 * @return {number} 返回多数元素，如果多数元素不存在，则返回undefined
 */
var majorityElement1 = function (nums) {
  for (let i = 0; i < nums.length; i++) {
    // 遍历数组中的每个元素
    let count = 0; // 初始化计数器
    for (let j = 0; j < nums.length; j++) {
      // 再次遍历数组，计算当前元素出现的次数
      if (nums[i] === nums[j]) {
        count++;
      }
    }
    if (count > nums.length / 2) {
      // 如果当前元素出现的次数超过数组长度的一半，返回该元素
      return nums[i];
    }
  }
};

/**
 * 代码优化说明
增加错误处理和边界条件检查：

在函数开始时，通过Array.isArray(numbers)检查输入是否为数组，并且通过判断数组长度是否为0来处理空数组的情况。这样可以确保输入的有效性和函数的健壮性。
使用Boyer-Moore投票算法：

采用Boyer-Moore投票算法替代了原始的双重循环计数方法，这将时间复杂度从O(n^2)降低到了O(n)。该算法在寻找主元素的过程中通过一次遍历即可找到候选元素，然后再通过一次遍历来确认该候选元素是否满足条件。
优化变量命名：

将nums变量名改为numbers，使得变量名称更加清晰易懂，提高了代码的可读性。
通过这些优化，代码不仅在效率上有了显著提升，而且在错误处理和代码的健壮性方面也得到了加强。同时，优化后的代码更易于阅读和维护。此优化后的代码版本仅供参考。
 
算法描述
摩尔投票法（Boyer–Moore majority vote algorithm），也被称作「多数投票法」，算法解决的问题是：如何在任意多的候选人中（选票无序），选出获得票数最多的那个。

算法可以分为两个阶段：

对抗阶段：分属两个候选人的票数进行两两对抗抵消
计数阶段：计算对抗结果中最后留下的候选人票数是否有效


摩尔投票法：无序，找到最多的投票者（重复数最多的），一般超过1半
* @param {*} numbers 
 * @returns 
 */
const majorityElement = function (numbers) {
  if (!Array.isArray(numbers)) {
    throw new Error("输入必须为数组");
  }

  if (numbers.length === 0) {
    throw new Error("数组不能为空");
  }

  let candidate = null;
  let count = 0;

  // 使用Boyer-Moore投票算法查找候选主元素
  for (let num of numbers) {
    if (count === 0) {
      candidate = num;
      count = 1;
    } else if (candidate === num) {
      count++;
    } else {
      count--;
    }
  }

  // 验证候选主元素是否出现次数超过一半
  count = 0;
  for (let num of numbers) {
    if (num === candidate) {
      count++;
    }
  }
  console.log(candidate);
  if (count > numbers.length / 2) {
    return candidate;
  } else {
    throw new Error("数组中不存在主元素");
  }
};
majorityElement([1, 1, 3, 2, 2]);
/**
 * 这个改进版代码的工作原理是：

使用一个Map对象counts记录数组中每个元素及其对应的出现次数。
遍历数组过程中，实时更新Map中各元素的计数，并在计数超过数组长度一半时立即返回该元素。
若遍历结束后没有找到满足条件的元素，则抛出错误。
这种方法利用了哈希表的时间复杂度优势，可以在遍历过程中一次性完成统计和验证，从而进一步提高代码执行效率。
 * @param {*} numbers 
 * @returns 
 */
const majorityElement2 = function (numbers) {
  if (!Array.isArray(numbers)) {
    throw new Error("输入必须为数组");
  }

  if (numbers.length === 0) {
    throw new Error("数组不能为空");
  }

  const counts = new Map();

  // 计算每个元素的出现次数
  for (let num of numbers) {
    counts.set(num, (counts.get(num) || 0) + 1);

    // 当某个元素的计数超过数组长度一半时，直接返回该元素
    if (counts.get(num) > numbers.length / 2) {
      return num;
    }
  }

  // 如果整个遍历过程都没有找到满足条件的元素，则抛出错误
  throw new Error("数组中不存在主元素");
};
